// -*- coding: utf-8 -*- 
/**
 * Project: AlgorithmsLearn
 *
 * @author: yanking
 * Create time: 2022-04-03 12:28
 * IDE: IntelliJ IDEA
 * Introduction:
 */
package com.LeetCodeT.BinaryAlgorithms;

import org.junit.jupiter.api.Test;

import java.util.HashMap;
import java.util.Map;

public class CountPairs {
    int mod = (int) 1e9 + 7, max = 1 << 22;

    /**
     * 大餐计数
     *
     * @param deliciousness
     * @return
     */
    public int countPairs(int[] deliciousness) {
        int n = deliciousness.length, ans = 0;
        Map<Integer, Integer> map = new HashMap<Integer, Integer>();
        for (int x : deliciousness) {
            for (int i = 1; i < max; i <<= 1) {
                int t = i - x;
                if (map.containsKey(t)) {
                    ans += map.get(t);
                    if (ans >= mod) {
                        ans -= mod;
                    }
                }
            }
            map.put(x, map.getOrDefault(x, 0) + 1);
        }
        return ans;
    }

    @Test
    public void shout() {
        int[] deliciousness = {64, 64, 64, 64, 64, 64, 64, 64, 64, 64, 64, 64, 64, 64, 64, 64, 64, 64, 64, 64, 64, 64, 64, 64, 64, 64, 64, 64, 64};
        System.out.println(countPairs(deliciousness));
    }
}
